﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using Flatland.GeneticProgramming.Compilation;
using Flatland.GeneticProgramming.CoreTypes;
using Flatland.GeneticProgramming.Crossovers;
using Flatland.GeneticProgramming.FileWriter;
using Flatland.GeneticProgramming.Initializations;
using Flatland.GeneticProgramming.Mutations;
using Flatland.GeneticProgramming.Selections;
using Flatland.Utilities;

/**
* 
* Copyright (c) 2012 Anders Høst Kjærgaard | ahkj@itu.dk
* 
* 
* Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
* associated documentation files (the "Software"), to deal in the Software without restriction, 
* including without limitation the rights to use, copy, modify, merge, publish, distribute, 
* sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is 
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all copies or substantial 
* portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT 
* NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 
* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

namespace Flatland.GeneticProgramming {
    /// <summary>
    /// Creates a genetic program subject to the GenoType and run-parameters provided.
    /// </summary>
    public class GP {
        /// <summary>
        /// GP output folder
        /// </summary>
        public static readonly string GP_OUTPUT_FOLDER_PREFIX = "GP";

        /// <summary>
        /// Temp output folder
        /// </summary>
        public static readonly string TEMP_FOLDER = "temp";

        /// <summary>
        /// Output file prefix
        /// </summary>
        public static readonly string OUTPUT_FILE_PREFIX = "GP";

        /// <summary>
        /// Default population size
        /// </summary>
        public const int DEFAULT_POPULATION_SIZE = 100;

        /// <summary>
        /// Default fitness goal
        /// </summary>
        public const int DEFAULT_FITNESS_GOAL = 10000;

        /// <summary>
        /// Default max generations
        /// </summary>
        public const int DEFAULT_MAX_GENERATIONS = 200;

        /// <summary>
        /// Default max tree depth
        /// </summary>
        public const uint DEFAULT_MAX_TREE_DEPTH = 7;

        /// <summary>
        /// Default mutation rate
        /// </summary>
        public const double DEFAULT_MUTATION_RATE = 0.05;

        /// <summary>
        /// Default cross over rate
        /// </summary>
        public const double DEFAULT_CROSS_OVER_RATE = 0.90;

        /// <summary>
        /// Default first generation
        /// </summary>
        public const int DEFAULT_FIRST_GENERATION = 1;

        /// <summary>
        /// Max command sequence. Number of sequential commands.
        /// </summary>
        public const int MAX_COMMAND_SEQUENCE = 3;

        /// <summary>
        /// Get or set the PrimitiveSet
        /// </summary>
        public PrimitiveSet primitiveSet { get; set; }

        /// <summary>
        /// Get or set the population
        /// </summary>
        public List<Report> Population { get; set; }

        /// <summary>
        /// Private. Current generation
        /// </summary>
        int _currentGeneration;

        /// <summary>
        /// Get current generation
        /// </summary>
        public int CurrentGeneration
        {
            get { return _currentGeneration; }
        }

        /// <summary>
        /// Average fitness history
        /// </summary>
        public double[] AverageFitnessHistory;

        /// <summary>
        /// Max fitness history
        /// </summary>
        public double[] MaxFitnessHistory;

        /// <summary>
        /// Fitness goal
        /// </summary>
        public readonly double FitnessGoal;

        /// <summary>
        /// Private epic breed
        /// </summary>
        Report _epicBreed;

        /// <summary>
        /// Population size
        /// </summary>
        public readonly uint PopulationSize;

        /// <summary>
        /// Max tree depth
        /// </summary>
        public readonly uint MaxTreeDepth;

        /// <summary>
        /// Max generations
        /// </summary>
        public readonly uint MaxGenerations;

        /// <summary>
        /// Run start time
        /// </summary>
        public static string RunStartTime;

        /// <summary>
        /// Get or set. True if no printed output
        /// </summary>
        public bool IgnoresOutput { get; set; }

        /// <summary>
        /// Crossover rate
        /// </summary>
        public readonly double CrossOverRate;

        /// <summary>
        /// Mutation rate
        /// </summary>
        public readonly double MutationRate;

        /// <summary>
        /// Mutation method
        /// </summary>
        public readonly MutationTechnique MutationTechnique;

        /// <summary>
        /// Selection method
        /// </summary>
        public readonly SelectionTechnique SelectionTechnique;

        /// <summary>
        /// Crossover method
        /// </summary>
        public readonly CrossoverTechnique CrossoverTechnique;

        /// <summary>
        /// Initialization method
        /// </summary>
        public readonly InitializationTechnique InitializationTechnique;
        
        /// <summary>
        /// If true GP will not call fitness on problem. 
        /// </summary>
        public bool EvaluateFitness;

        /// <summary>
        /// Compiler
        /// </summary>
        private readonly Compiler _compiler;

        /// <summary>
        /// Crossover
        /// </summary>
        private readonly ICrossOver _crosser;

        /// <summary>
        /// Selection
        /// </summary>
        private readonly ISelection _selection;

        /// <summary>
        /// Initializtion
        /// </summary>
        private readonly IInitialization _initialization;

        /// <summary>
        /// Mutation
        /// </summary>
        private readonly IMutation _mutation;

        //stop watches
        public Stopwatch SwCrossOver, SwMutation, SwSelection, SwFitness, SwRunTime;

        /// <summary>
        /// Private. Use the parameterized constructor instead.
        /// </summary>
        private GP() { }

        /// <summary>
        /// GenoType we are evolving
        /// </summary>
        readonly GenoType _genoType;

        /// <summary>
        /// Private. True if the population has been initialized
        /// </summary>
        bool _initialized;

        /// <summary>
        /// Constructor equalivant to an initialization step of a genetic program run with default run-parameters.
        /// </summary>
        /// <param name="genoType">The genoType defining the PrimitiveSet to be evolved</param>
        /// <param name="fitnessGoal">Desired fitness goal for this instace run.</param>
        /// <param name="populationSize">Initial population size</param>
        /// <param name="maxTreeDepth">Max depth of expression Tree. Treated by the strategies.</param>
        /// <param name="maxGenerations">Max number of generations instance run.</param>
        /// <param name="mutationTechnique">MutationTechnique for this instance run.</param>
        /// <param name="selectionTechnique">SelectionTechnique for this instance run.</param>
        /// <param name="crossoverTechnique">CrossoverTechnique for this instance run.</param>
        /// <param name="mutationRate">Rate of mutation occuring 0 being never and 1 being always. Treated by the MutationOverStrategy. </param>
        /// <param name="crossOverRate">Rate of crossover occuring 0 being never and 1 being always. Treated by the CrossoverTechnique.</param>
        public GP(GenoType genoType,
                       double fitnessGoal = DEFAULT_FITNESS_GOAL,
                       uint populationSize = DEFAULT_POPULATION_SIZE,
                       uint maxTreeDepth = DEFAULT_MAX_TREE_DEPTH,
                       uint maxGenerations = DEFAULT_MAX_GENERATIONS,
                       MutationTechnique mutationTechnique = MutationTechnique.Subtree_Replacement,
                       double mutationRate = DEFAULT_MUTATION_RATE,
                       SelectionTechnique selectionTechnique = SelectionTechnique.TOURNAMENT,
                       CrossoverTechnique crossoverTechnique = CrossoverTechnique.ONE_POINT_CROSS_OVER,
                       double crossOverRate = DEFAULT_CROSS_OVER_RATE,
                       InitializationTechnique initializationTechnique = InitializationTechnique.RampedHalfAndHalf) {

            _currentGeneration = 1;
            FitnessGoal = fitnessGoal;
            PopulationSize = populationSize;
            MaxGenerations = maxGenerations;
            MaxTreeDepth = maxTreeDepth;
            MutationTechnique = mutationTechnique;
            SelectionTechnique = selectionTechnique;
            Population = new List<Report>((int)PopulationSize);
            CrossoverTechnique = crossoverTechnique;
            CrossOverRate = crossOverRate;
            MutationRate = mutationRate;
            EvaluateFitness = true;
            MutationTechnique = mutationTechnique;
            InitializationTechnique = initializationTechnique;
            RunStartTime = Utils.GetTimeStamp();
            _genoType = genoType;

            primitiveSet = new PrimitiveSet();
            primitiveSet.Parse(genoType);
            _compiler = new Compiler(GP_OUTPUT_FOLDER_PREFIX + RunStartTime);

            /*
             *  Run elements with the desired strategies.
             */
            _crosser = new Crossover(CrossoverTechnique);
            _selection = new Selection(SelectionTechnique);
            _initialization = new Initialization(InitializationTechnique);
            _mutation = new Mutation(MutationTechnique);

            /*
             *  Run statistics
             */
            AverageFitnessHistory = new double[MaxGenerations];
            MaxFitnessHistory = new double[MaxGenerations];

            /*
             *  Run timers
             */
            SwCrossOver = new Stopwatch();
            SwMutation = new Stopwatch();
            SwSelection = new Stopwatch();
            SwFitness = new Stopwatch();
            SwRunTime = new Stopwatch();

            var d = Directory.CreateDirectory(TEMP_FOLDER);
            d.Attributes &= ~FileAttributes.ReadOnly;
        }


        /// <summary>
        /// Initialized the population. This must be called prior to Evolve
        /// </summary>
        public void Init() {
            SwRunTime.Start();
            //Init _population
            _epicBreed = new Report();
            for (int i = 0; i < PopulationSize; i++) {
                Report report = new Report();
                report.GenoType = (GenoType)_genoType.Clone();
                report.GenoType.Tree = _initialization.Init(MaxTreeDepth, primitiveSet);
                report.PrimitiveSet = primitiveSet;
                report.Generation = CurrentGeneration;
                if(EvaluateFitness)
                  report.Fitness = report.GenoType.Fitness();
                Population.Add(report);
            }
            _epicBreed = MaxFitness();
            _initialized = true;
        }

        /// <summary>
        /// Run the genetic algorithm and returns a GenoType with the run result.
        /// First the population needs to be initialized
        /// 1 We repeat the following steps until a 'goal test' is satified
        /// 2 Selection - to programs to be used in the next generation
        /// 3 Crossover - some programs will breed new programs
        /// 4 Mutation  - some programs will mutate  
        /// </summary>
        public GenoType Run() {
            Debug.Assert(Population != null, "Population was null when calling Run");
            Init();
            if (PopulationSize == 0) {
                return _genoType;
            }
               
            _epicBreed = MaxFitness();
            while (Evolve()) {
                Debug.Assert(Population != null, "Population was null during Run");
                Debug.Assert(!(from p in Population where p.PrimitiveSet == null select p).Any(), "Report missing PrimitiveSet during run");
                Debug.Assert(!(from p in Population where p.GenoType == null select p).Any(), "Report missing GenoType during run");
                Debug.Assert(!(from p in Population where p.GenoType.Tree == null select p).Any(), "Report missing Tree during run");
            }

            Debug.Assert(_epicBreed != null, "Epic breed returned from run was null", "This may happen if previous steps where not carried out correctly.");
            return _epicBreed.GenoType;
        }

        /// <summary>
        /// Evolve the population. Returns true if population is evolved. False if a goal test passes.
        /// </summary>
        /// <returns></returns>
        public bool Evolve() {
            if (Population.Count == 0) throw new MethodAccessException("You must init or set a population before calling evolve");
            SwFitness.Stop();//Last StopWatch started, must be here if fitness is calculated by caller
            Report bestBreed = MaxFitness();
            if (_epicBreed.Fitness <= bestBreed.Fitness) {
                _epicBreed = bestBreed;
            }
            MaxFitnessHistory[CurrentGeneration-1] = _epicBreed.Fitness;
            AverageFitnessHistory[CurrentGeneration-1] = AverageFitness();

            Console.WriteLine("Max: {0} Avg: {1} Generation: {2}", _epicBreed.Fitness, AverageFitnessHistory[CurrentGeneration - 1], CurrentGeneration);

           if (GoalTest())
                return false;
            if (UserPreferences.VERBOSE)
                PrintPopulation(Population);

            SwSelection.Start();
            List<Report> newPop = _selection.Select(Population);
            SwSelection.Stop();

            SwCrossOver.Start();
            if (1 < PopulationSize)
                _crosser.Cross(newPop, CrossOverRate, (int) MaxTreeDepth);
            SwCrossOver.Stop();

            SwMutation.Start();
            _mutation.Mutate(newPop, MutationRate, (int) MaxTreeDepth);
            SwMutation.Stop();

            for (int i = 0; i < PopulationSize; i++) {
                SwFitness.Start();
                if (EvaluateFitness) {
                    newPop[i].Fitness = newPop[i].GenoType.Fitness();
                    SwFitness.Stop();
                }
                newPop[i].Generation = CurrentGeneration;
            }
            Population = newPop;
            ++_currentGeneration;
            Debug.Assert(newPop != null, "New population was null during Run");
            return true;
        }

        /// <summary>
        /// Returns true if a desired goal has been met and outputs the run result. 
        /// </summary>
        /// <returns></returns>
        private bool GoalTest() {
            Debug.Assert(_epicBreed != null, "_epicBreed was null in Goaltest");
            if (FitnessGoal <= _epicBreed.Fitness || MaxGenerations <= CurrentGeneration) {
                SwRunTime.Stop();
                if(!IgnoresOutput){
                    _compiler.Compile(_epicBreed, "Epic_" + _epicBreed.GenoType.GetType().Name + "_Gen_" + CurrentGeneration, true);
                    new RunResultWriter(this, _epicBreed).Write(_compiler.OutputNamespace);
                    var gf = new GeneFileWriter();
                    _epicBreed.FilePath = gf.Serialize(_epicBreed);
                }
                return true;
            }
            return false;
        }

        /// <summary>
        /// Finds and prints the max fitness value from the population
        /// </summary>
        private double AverageFitness(List<Report> pop = null, int gen = -1) {
            if (pop == null) pop = Population;
            if (gen == -1) gen = CurrentGeneration;
            Debug.Assert(pop != null, "Population was null in AverageFitness");
            double avg = 0;
            double weight = 1d / pop.Count; //Weigh every fitness to avoid overflow
            foreach (Report rep in pop)
                avg += rep.Fitness * weight;
            if (UserPreferences.VERBOSE)
                Console.WriteLine("Average fitness was {0} in generation {1}", avg / pop.Count, gen);
            return avg;
        }

        /// <summary>
        /// Finds the max fitness value from a population
        /// </summary>
        private Report MaxFitness() {
            int count = Population.Count;
            Debug.Assert(0 < count, "Population size was not above zero in MaxFitness");
            Debug.Assert(Population != null, "Population was null in MaxFitness");
            Report max = Population[0];
            for (int i = 1; i < count; i++) {
                if (max.Fitness < Population[i].Fitness)
                    max = Population[i];
            }
            if (UserPreferences.VERBOSE)
                Console.WriteLine("Max fitness was {0} \nReport: {1}", max.Fitness, max);
            return max;
        }

        /// <summary>
        /// Prints a detailed summary of a population to the console
        /// </summary>
        private void PrintPopulation(List<Report> pop = null) {
            if (pop == null) pop = Population;
            foreach (Report rep in pop) {
                Console.WriteLine("Class: {0} - Fitness: {1} - \nReport HashCode: {2}\nTree Hashcode {3}",
                                  rep.GenoType.GetType(), rep.Fitness, rep.GetHashCode(), rep.GenoType.Tree.GetHashCode());
                rep.GenoType.Tree.PrintTree();
            }
        }
    }
}
